
"""
3.无重复字符的最长子串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
"""


class Solution:

    def method1(self, s: str) -> int:
        """
        暴力解法
        """
        if not s:
            return 0

        size = len(s)
        max_val = 1  # 非空子串，至少自身是1个
        # 要测试多少轮
        for i in range(size):
            res = 0
            tmp_set = set()
            # 每轮从第i个元素开始
            for j in range(i, size):
                if s[j] not in tmp_set:
                    tmp_set.add(s[j])
                    res += 1
                else:
                    break
            
            # 从i位置开始的子串，有几个是不重复的在res里
            max_val = max(res, max_val)

        return max_val

    def method2(self, s: str) -> int:
        """
        滑动窗口解法
        """
        if not s:
            return 0

        size = len(s)
        max_val = 1 # 非空字符串，自身至少算1个
        
        j = 0  # 初始化指针，用来移动窗口
        visited = []  # 记录看过的元素
        tmp_res = 0
        while j < size:
            if s[j] not in visited:  # 如果字符没见过，就加入到visited中
                visited.append(s[j])
                tmp_res += 1
            else:
                max_val = max(max_val, tmp_res)
                # 找到前面对应s[j]的值的位置, 把这之前的数据全部踢掉,重新计算visited
                idx = visited.index(s[j])
                visited = visited[idx+1:]
                # 并把当前的的s[j]加入
                visited.append(s[j])
                # 更新tmp_res为当前visited的长度
                tmp_res = len(visited)

            j += 1  # j走1个位置

        # 最后还要再比一次
        max_val = max(max_val, tmp_res)
        
        return max_val


    def lengthOfLongestSubstring(self, s: str) -> int:
       return self.method1(s)

def test():
    obj = Solution()
    res = obj.lengthOfLongestSubstring("au")
    print(res)


if __name__ == "__main__":
    test()
